import java.util.Arrays;

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n];

        int lenest=1;
        int[] count=new int[n];
        int ret=0;


        for(int i=0;i<n;i++){
            dp[i]=1;
            count[i]=1;

            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){

                    if(dp[i]<dp[j]+1){
                        dp[i]=dp[j]+1;
                        count[i]=count[j];

                    }else if(dp[i]==dp[j]+1){
                        count[i]+=count[j];
                    }

                }



            }

            if(dp[i]>lenest){
                lenest=dp[i];
                ret=count[i];

            } else if (dp[i]==lenest) {
                ret+=count[i];

            }

        }
        return ret;
    }
}





//贪心解法
class Solution1 {
    public int findLongestChain(int[][] pairs) {
        // 按照数对的第二个元素（结束值）进行排序
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);

        int count = 1; // 至少可以形成一个链
        int lastEnd = pairs[0][1]; // 记录当前链最后一个数对的结束值

        for (int i = 1; i < pairs.length; i++) {
            // 如果当前数对的开始值大于上一个数对的结束值
            if (pairs[i][0] > lastEnd) {
                count++; // 链长度加1
                lastEnd = pairs[i][1]; // 更新最后一个数对的结束值
            }
        }

        return count;
    }
}

//动态规划解法
class Solution11 {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs,(a,b)->a[1]-b[1]);
        int n=pairs.length;
        int[] dp=new int[n];
        int ret=0;
        for(int i=0;i<n;i++){
            dp[i]=1;
            for(int j=0;j<i;j++){
                if(pairs[i][0]>pairs[j][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }

            }
            ret=Math.max(dp[i],ret);
        }

        return ret;


    }
}



//最长公共子序列(在字符串前补充长度，随便什么都行)
class Solution3 {
    public int longestCommonSubsequence(String text1, String text2) {
        String t1=" "+text1;
        String t2=" "+text2;

        int m=t1.length();
        int n=t2.length();

        int dp[][]=new int[m][n];

        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                if(t1.charAt(i)==t2.charAt(j)) dp[i][j]=dp[i-1][j-1]+1;
                else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[m-1][n-1];
    }
}



//两个数组的dp，不相交的线
class Solution2 {
    public int maxUncrossedLines(int[] t1, int[] t2) {


        int m=t1.length;
        int n=t2.length;

        int dp[][]=new int[m+1][n+1];

        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(t1[i-1]==t2[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }

        return dp[m][n];


    }
}



class Solution4 {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        int mod = (int)1e9+7;

        // 使用动态规划表，dp[i][j]表示s[0..i-1]中t[0..j-1]出现的次数
        int[][] dp = new int[m+1][n+1];

        // 空字符串是任何字符串的子序列
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i-1) == t.charAt(j-1)) {
                    // 当字符匹配时，可以选择使用或不使用s的当前字符
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod;
                } else {
                    // 不匹配时，只能选择不使用s的当前字符
                    dp[i][j] = dp[i-1][j] % mod;
                }
            }
        }

        return dp[m][n];
    }
}